package br.com.rookgraph;

import br.com.rookgraph.BranchReduceIR.Aresta;

/**
 * Implementação do Algoritimo de IR. Extraido do artigo: "Abordagem de
 * Refinamento interativo para o problema da árvore geradora com número mínimo
 * de vertices Branches." Diego Mello da Silva
 *
 *
 * @author Luan Pontes
 * @since 5-10-12
 *
 */
public class BranchReduce {

	private Graph original;
	private Graph tree;
	private final boolean useIR;

	public BranchReduce(Graph original, Graph tree, boolean useIR) {
		super();
		this.original = original;
		this.tree = tree;
		this.useIR = useIR;
	}

	public Graph execute() {

		Graph graphBest = this.tree;
		boolean replaceEdge;
		do {
			replaceEdge = false;

			Edge[] listCut = createCuttingList();

			Edge[] listRep;
			while (!replaceEdge && listCut.length != 0) {

				Edge edgeCut = selectCutEdge(listCut);

				this.tree.removeEdge(edgeCut);
				listCut = removeEdgeList(edgeCut, listCut);
				listRep = createReplacementListToCuttingEdge(edgeCut);
				Edge replace = selectEdgeFromReplamentList(listRep, edgeCut);

				if (replace != null) {
					this.tree.addEdge(replace);
					replaceEdge = true;
					if (isTreeBest(graphBest)) {
						try {
							graphBest = (Graph) this.tree.clone();
						} catch (CloneNotSupportedException e) {
							e.printStackTrace();
						}
					}
				} else {
					this.tree.addEdge(edgeCut);
				}
			}
		} while (replaceEdge);
		return graphBest;
	}

	public boolean isTreeBest(Graph graphBest) {
		return this.tree.getBranchs().length < graphBest.getBranchs().length;
	}

	public Edge[] removeEdgeList(Edge arestCut, final Edge[] list) {
		int count = 0;
		for (int i = 0; i < list.length; i++) {
			if (list[i].equals(arestCut)) {
				list[i] = null;
				count++;
				for (int j = i; j < list.length - 1; j++) {
					list[j] = list[j + 1];
				}
			}
		}
		int length = list.length - count;
		Edge[] newList = new Edge[length];
		System.arraycopy(list, 0, newList, 0, length);
		return newList;
	}

	protected Edge selectEdgeFromReplamentList(final Edge[] listRep, Edge edgeCut) {

		Edge edgeRep = null;
//		Edge edgeRepEscolhida = null;
//		int sigmaEdgeRep = 1, alfaEdgeRep = -1;

		for (Edge candidate : listRep) {

			this.tree.addEdge(candidate);

			candidate.alfa = this.tree.alfa(candidate.origin,candidate.target);
			candidate.sigma = this.tree.sigma(candidate.origin,candidate.target);

			//remove aresta adicionada para calculo de alfa e sigma
			this.tree.removeEdge(candidate);

			if (edgeRep == null || candidate.alfa < edgeRep.alfa) {

				edgeRep = candidate;

			} else if (candidate.alfa == edgeRep.alfa) {

				if(changeEdgeRep(edgeRep.sigma, candidate.sigma)){
					edgeRep = candidate;
				}

			}

			//this.tree.removeEdge(candidate);
//			edgeRepEscolhida = candidate;
		}

		// precisa checar aqui se de fato a aresta será substituida. ela só será se for vantajoso, conforme a escolha de sigma
		// para isso é preciso conhecer os valores de alga e sigma da aresta que foi cortada e comparar com o que irá subsituir
	    // ver algoritmo original

//		if (useIR) {
//			if (alfaEdgeRep < alfaCut){
//				edgeRep = edgeRepEscolhida;
//			}
//			else if (alfaEdgeRep == alfaCut && sigmaEdgeRep < sigmaCut){
//				edgeRep = edgeRepEscolhida;
//			}
//			else {
//				edgeRep = null;
//			}
//		}
//		else {
//			if (alfaEdgeRep < alfaCut){
//				edgeRep = edgeRepEscolhida;
//			}
//			else if (alfaEdgeRep == alfaCut && sigmaEdgeRep > sigmaCut){
//				edgeRep = edgeRepEscolhida;
//			}
//				else {
//					edgeRep = null;
//			}
//		}

		return edgeRep != null && isVatanjoso(edgeRep, edgeCut)? edgeRep : null;
	}

	private boolean isVatanjoso(Edge rep, Edge cut) {
		if (useIR){
			return (rep.alfa < cut.alfa) || (rep.alfa == cut.alfa && rep.sigma < cut.sigma) ;
		}else{
			return (rep.alfa < cut.alfa) || (rep.alfa == cut.alfa && rep.sigma > cut.sigma) ;
		}
	}

	public boolean changeEdgeRep(int sigmaEdgeRep, int sigmaCandidate) {
		if (useIR){
			return sigmaCandidate < sigmaEdgeRep;
		}else{
			return sigmaCandidate > sigmaEdgeRep;
		}
	}

	protected Edge[] createReplacementListToCuttingEdge(final Edge arestaCut) {

		int[] seg1 = this.tree.reached(arestaCut.origin, new int[this.tree.getOrder()]);
		int[] seg2 = this.tree.reached(arestaCut.target, new int[this.tree.getOrder()]);

		// TODO verificar tamanho dessa lista por um teorema.
		Edge[] arestasRep = new Edge[seg1.length * seg2.length];

		int count = 0;
		/* Comparar arestas dos segmentos com as do grafo original */

		for (int vSeg1 : seg1) {
			for (int vSeg2 : seg2) {

				final Edge currentArest = new Edge(vSeg1, vSeg2);

				if (!currentArest.equals(arestaCut)) {

					if (!this.tree.hasEdge(vSeg1, vSeg2)
							&& this.original.hasEdge(vSeg1, vSeg2)) {

						currentArest.alfa = this.tree.alfa(currentArest.origin,currentArest.target);
						currentArest.sigma = this.tree.sigma(currentArest.origin, currentArest.target);

						// if( currentArest.alfa < arestaCut.alfa){

						arestasRep[count++] = currentArest;
						//
						// }else if(currentArest.alfa == arestaCut.alfa){
						// if( currentArest.sigma < arestaCut.sigma){
						// arestasRep[count++] = currentArest;
						// }

						// }

					}

				}
			}
		}

		Edge[] listRep = new Edge[count];
		System.arraycopy(arestasRep, 0, listRep, 0, count);

		return listRep;
	}

	/**
	 * Seleciona dentre as candidatas a melhor aresta para coste.
	 *
	 * @param listRep
	 * @return
	 */
	protected Edge selectCutEdge(final Edge[] listCut) {

		Edge edgeCut = null;
		for (Edge candidate : listCut) {

			candidate.alfa = this.tree.alfa(candidate);
			candidate.sigma = this.tree.sigma(candidate);

			if (edgeCut == null || candidate.alfa > edgeCut.alfa) {

				edgeCut = candidate;

			} else {
				if (candidate.alfa == edgeCut.alfa) {

					if(changeEdgeCut(edgeCut.sigma, candidate.sigma)){
						edgeCut =  candidate;
					}
				}
			}
		}

		return edgeCut;
	}

	private boolean changeEdgeCut(int sigmaCut, int sigmaCandidate) {
          if(this.useIR){
        	  return sigmaCandidate > sigmaCut;
          }else{
        	  return sigmaCandidate < sigmaCut;
          }
	}

	/**
	 * Cria a lista de arestas candidatas a corte.
	 *
	 * @return
	 */
	protected Edge[] createCuttingList() {
		int order = tree.getOrder();
		int count = 0;
		Edge[] edgesCut = new Edge[order * order];

		for (int branch : this.tree.getBranchs()) {
			for (int adjacente : this.tree.getAdjacentes(branch)) {

				Edge candidata = new Edge(branch, adjacente);

				if (!conteins(candidata, edgesCut)) {
					edgesCut[count++] = candidata;
				}
			}
		}

		Edge[] listCut = new Edge[count];
		System.arraycopy(edgesCut, 0, listCut, 0, count);
		return listCut;
	}

	private boolean conteins(Edge candidata, Edge[] edgesCut) {

		for (Edge aresta : edgesCut) {
			if (aresta != null && aresta.equals(candidata))
				return true;
		}

		return false;
	}

	public Graph getOriginal() {
		return original;
	}

	public void setOriginal(Graph original) {
		this.original = original;
	}

	public Graph getTree() {
		return tree;
	}

	public void setTree(Graph tree) {
		this.tree = tree;
	}

	public boolean isUseIR() {
		return useIR;
	}

}